class Solution {
public:
    int inf = 1000000000;
    bool flag[105][105];
    int dp[105][105];
    int minCost(int n, vector<int>& cuts) {
        sort(cuts.begin(), cuts.end());
        cuts.insert(cuts.begin(), 0);
        cuts.push_back(n);
        return dfs(0, cuts.size() - 1, cuts);
    }
    int dfs(int l, int r, vector<int>& num)
    {
        if (l + 1 >= r) return 0;
        if (flag[l][r]) return dp[l][r];
        int ans = inf;;
        for (int i = l + 1; i < r; i++)
        {
            ans = min(ans, dfs(l, i, num) + dfs(i, r, num) + num[r] - num[l]);
        }
        flag[l][r] = 1;
        return dp[l][r] = ans;
    }
};